'''
https://leetcode.cn/problems/house-robber-iii/
'''
from functools import cache
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # dp 记忆化搜索
    # 尝试 + cache， 尝试可能每个节点会走多次，特别是底层节点+cache以缓存
    def rob(self, root: Optional[TreeNode]) -> int:
        @cache
        def process(cur):
            if not cur: return 0
            # 当前不偷
            ans1 = process(cur.left) + process(cur.right)
            # 如果当前可以偷
            ans2 = cur.val
            if cur.left:
                ans2 += process(cur.left.left) + process(cur.left.right)
            if cur.right:
                ans2 += process(cur.right.left) + process(cur.right.right)
            return max(ans1, ans2)
        return process(root)

    # dfs，每个节点都访问一次
    def rob2(self, root: Optional[TreeNode]) -> int:
        def dfs(cur):
            if not cur: return 0, 0
            l1, l2 = dfs(cur.left)
            r1, r2 = dfs(cur.right)
            res1 = cur.val + l2 + r2
            res2 = max(l1, l2) + max(r1, r2)    # 当前不偷，左边可偷可不偷，右边同理
            return res1, res2
        return max(dfs(root))

